1. Field of the Invention
The present invention relates to a method of inserting supplementary information such as a secret mark in a digital signal.
It also concerns a method of extracting a secret mark inserted in a digital signal.
Correlatively, the present invention concerns a device for inserting supplementary information and a device for extracting supplementary information, adapted respectively to implement the insertion and extraction methods according to the invention.
2. Description of the Related Art
The digital signal considered hereinafter will more particularly be a sequence of digital images.
The insertion and extraction methods according to the invention lie within the technical field of the watermarking of digital data, which can be interpreted as the insertion of a seal in the digital data, making it possible for example to authenticate the content of a digital data file. This watermarking is also referred to as digital tattooing.
Watermarking entails in general terms the modification of coefficients representing the digital image. This modification is imperceptible to the eye, but can be decoded by an appropriate decoder.
Conventionally, to insert a binary message into a digital image, the bits of the message are first of all modulated by a noise sequence little correlated with the image. The noise sequence is a pseudo-random signal. This modulated message is next weighted so that it remains invisible after insertion in the image.
For the later extraction of the message, the same noise sequence is re-used. This noise sequence is correlated with the difference between the image in which the message has been inserted and an estimation of the initial image. This calculation makes it possible to recover the value of each bit inserted, and all the better with the estimation of the initial image being correct.
The document U.S. Pat. No. 5,933,798 proposes to improve the detection of a message inserted in a video signal by filtering the signal in which that message has been inserted. This filtering is spatial filtering, or in other words an intra-image prediction. The time dimension of the signal is not used.
The document U.S. Pat. No. 5,991,426 relates to the insertion of a message in video images. Such an image comprises an even field and an odd field which are strongly correlated. The insertion takes this into account for inserting the message in a particular manner in order to reduce the noise due to the image on extraction of the message.
The article entitled “A robust frame-based technique for video watermarking” by R. Caldelli, M. Barni, F. Bartolini and A. Piva, which appeared in Eusipco 2000, describes an algorithm for message insertion in a video. One image out of X images is used, where X is any integer, the value 9 being often used. The fact of not using all the images makes it possible to increase the statistical invisibility and the message is more difficult to predict. Prior to the insertion, the images are transformed by a discrete Fourier transformation. The extraction of the message is carried out by correlation measurement through individually processing each image of the video.
3. Brief Summary of the Invention
In the preceding examples the time dimension of the signal is not used.
In a first aspect, the object of the present invention is to improve the estimation of the initial image on the extraction of a message in such a manner as to increase the quality of the extraction of the message.
For this, the invention provides a method and a device for insertion of a message in a sequence of digital images which use the time dimension of the image sequence.
More particularly, the invention provides a method of inserting a message in a sequence of digital images, characterized in that it comprises the insertion, in the spatial domain, of at least one symbol of the message in at least one part of an image, said image being bounded between two images in which no symbol is inserted in their respective parts in spatial correspondence with said part.
Correlatively, the invention relates to a device for inserting a message in a sequence of digital images, characterized in that it comprises means for inserting, in the spatial domain, at least one symbol of the message in at least one part of an image, said image being included between two images in which no symbol is inserted in their respective parts in spatial correspondence with said part.
The invention makes it possible, on the later extraction of a message, to improve the estimation of the initial image and so favor the correct prediction of the message. Indeed, the zones in which message symbols are inserted are always bounded temporally by zones in which no insertion is made.
According to a preferred feature, the insertion is carried out on one image out of every two. This implementation is particularly simple, since a symbol can be inserted over the entirety of an image, this image being bounded by two images in which no insertion has been carried out. This implementation is simple and gives satisfactory results.
The insertion device comprises means for implementing the above features.
According to a preferred feature, the invention comprises the modulation of a symbol to be inserted by a pseudo-random sequence and the insertion of the result in said at least one part of an image.
The invention also relates to a method of extracting a message from a sequence of images in which the message has been inserted by the method of insertion already set out, characterized in that it comprises, for an image part in which at least one symbol has been inserted, the steps of:                predicting the current image part from the respective parts in spatial correspondence of the two images bounding it,        subtracting the part of the image predicted from the part of the image in which at least one symbol has been inserted, and        extracting the at least one symbol from the result of the subtraction.        
The prediction makes it possible to obtain an estimation of the image which is close to the initial image, which enables a good quality of detection and of extraction of the message.
According to a preferred feature, the prediction of the current image part is performed by a calculation of the mean of the respective parts in spatial correspondence of the two images bounding it or by a calculation of the movement between the current image part and the respective parts in spatial correspondence of the two images bounding it.
According to a preferred feature, at the time of the subtraction, only the values resulting from the subtraction which are less than a predetermined threshold are kept. This is because this enables the extreme values to be eliminated which contributes to correct extraction of the message.
According to a preferred feature, the extraction comprises a calculation of correlation between the result of the subtraction and the pseudo-random sequence used at the time of the insertion.
The insertion of a message is said to be robust if the message can later be extracted even if the image has undergone transformations such as compression and/or geometrical distortions and/or time truncation and/or modification of a component of the pixels of the image, for example modification of the luminance. The term time truncation is used herein to mean the deletion of images at the start or at the end of the video sequence.
In order to establish the ideas, FIG. 24 represents a sequence of digital images VD. All the images of the sequence have the same size of H×L pixels, where H and L are integers.
The sequence VD is transformed into the sequence VD1, of which the images all have a size of H′×L′ pixels, where H′ is less than H and L′ is less than L. In other words, only one part of each original image is kept.
The sequence VD is transformed into the sequence VD2 by interpolation, of which the images represent the same content as the original images, but with different dimensions: H″×L″ pixels.
For example, the document U.S. Pat. No. 5,809,139 describes the insertion of a message in a video sequence. The message is inserted by modulation of each of its bits by a pseudo-random sequence.
A geometrical modification of the images of the video after insertion leads to a loss in the synchronization with the demodulation sequence. It then becomes impossible to extract the message.
The article entitled “A geometrical and frequential watermarking scheme using similarities” of P. Bas, J. M. Chassery and F. Davoine which appeared in SPIE conference on security and watermarking of multimedia contents, San Jose, Calif., Vol. 3657, January 1999, deals with watermarking of fixed images.
In this document, characteristic points of the image are detected. Square blocks are formed around these points. The image is watermarked by adding to one of the other blocks the texture of the block in which the detected point is to be found.
The watermarking signal is thus created from the image. However, this technique does not enable a message to be inserted in the image. Moreover, this watermarking is not robust in relation to numerous geometrical modifications of the image following watermarking.
The techniques presented in these two documents do not vary and are consequently robust with respect to the changes of a component of the pixels of the image. On the other hand, as already stated, they are not robust with respect to geometrical modifications.
The article entitled “Dither modulation : a new approach to digital watermarking and information embedding” by B. Chen and G. W. Wornell, which appeared in SPIE conference on security and watermarking of multimedia contents, San Jose, Calif., Vol. 3657, January 1999, deals with a method of watermarking of an image based on a uniform quantization of the pixels of the image. The quantization mode is chosen as a function of the value of the bit that it is desired to insert in the image.
This technique is robust to geometrical modifications of the image following watermarking. However, the inventor has determined by means of tests that this technique is less robust than the present invention to MPEG (Motion Picture Expert Group) compression.
Furthermore, this technique is not robust with respect to changes in the components of the pixels of the image, such as modification of the luminance value.
In the case of a time truncation of the digital sequence of images in which a message has been inserted, that is to say images have been deleted in particular at the start of the sequence, the message which is later extracted from the sequence is offset with respect to the message which had been inserted. It is thus necessary to perform a time re-synchronization of the extracted message.
The three prior documents do not deal with this problem.
The document entitled “A robust Frame-Based Technique for video watermarking” which appeared at Eucipco, Tampere, Finland, in September 2000, presents an algorithm for video watermarking which is robust to certain geometric distortions. Generally, one image out of every twelve is watermarked. On account of this, it is important to find the watermarked images again when a time truncation appears. To do this, a correlation measurement is calculated between each image of the video and a reference watermarking signal, which is done even if the majority of the images are not watermarked. The video is considered to be watermarked if images of the video present a correlation peak greater than a threshold. The time localization of these peaks is of little importance; only their presence shows the presence of the watermarking searched for. This algorithm does not therefore require any time synchronization and consequently does not deal with this question.
Furthermore, in this document, only the reference watermarking signal is searched for. This algorithm is thus difficult to implement when the number of possible messages is very high. Indeed, if the number of watermarks searched for is high, for example 2^64, then 2^64 correlation measurements must be carried out. This number is too high to be able to be implemented in practice.
In the document entitled “Digital watermarking of raw and compressed video” by F. Hartung and B. Girod which appeared in SPIE, Digital Compression Technologies and Systems For video Communication, October 1996, Berlin, a method of watermarking by spectrum spreading is presented. In case of time truncation, the authors mention a mechanism based on a “sliding correlator” to recover the time synchronization.
However, this document does not deal with the question of geometrical distortions. The synchronization presented in this document is ineffective when the time truncation is associated with a geometrical distortion.
Thus, none of the prior documents presents a technique for message insertion which is both robust to geometrical distortions as well as enabling a time re-synchronization to be carried out on the extraction of the message so as to eliminate the effect of a time truncation.
In a second aspect, the object of the present invention is to remedy the drawbacks of the prior art, by providing a method and device for inserting a message in a sequence of digital images which is robust with respect to geometrical modifications and to the operations of compression and decompression.
To this end, the invention provides a method of inserting a message in a sequence of digital images, characterized in that it comprises, for each image in which a symbol of the message is to be inserted, the steps of:                determining a modulation sequence from a reference image included in the sequence of images,        modulating the symbol to be inserted by the determined modulation sequence,        inserting the modulated symbol in the current image.        
The invention permits an insertion that is robust to geometrical distortions and to compression and decompression operations.
According to a preferred feature, the reference image is the image following the current image in the sequence. This feature is simple to implement.
According to a preferred feature, the insertion is carried out in one image out of every two. This implementation is particularly simple, since a symbol can be inserted over the entirety of an image, this image being bounded by two images in which no insertion has been carried out. This implementation is simple and gives satisfactory results.
According to a preferred feature, the determination of a modulation sequence comprises:                performing integer division of the value of a predetermined component of each pixel of the reference image, by a first predetermined value,        comparing the remainder of the integer division with a predetermined value, for each integer division,        determining the value of each coefficient of the modulation sequence, depending on the respective result of each comparison.        
The invention also relates to a method of extracting a message from a sequence of images in which the message has been inserted by the method of insertion already set out, characterized in that it comprises, for an image in which a symbol has been inserted, the steps of:                estimating the watermarking signal of the inserted symbol,        determining a demodulation sequence from a reference image,        demodulating the estimated watermarking signal with the demodulation sequence.        
According to a preferred feature, the estimation of the watermarking signal of the inserted symbol comprises the steps of:                time prediction of a current image from the two images bounding it, and        subtraction of the predicted image from the current image.        
According to a preferred feature, the prediction of the current image is performed by a calculation of the mean of the two images bounding it.
In a complementary manner, the invention relates to a device for the insertion of a message in a sequence of digital images, characterized in that is comprises:                means for determining a modulation sequence from a reference image included in the sequence of images, for each image in which a symbol of the message is to be inserted,        means for modulating the symbol to be inserted by the determined modulation sequence,        means for inserting the modulated symbol in the current image.        
The insertion device comprises means for implementing the above features.
The invention also relates to a device for extracting a message from a sequence of images in which the message has been inserted by the insertion device already presented, characterized in that it comprises:                means for time prediction of a current image from the two images bounding it, and        means for subtraction of the predicted image from the current image,        means for determining a demodulation sequence from a reference image,        means for demodulation of the result of the subtraction by the demodulation sequence.        
In a third aspect, the object of the present invention is to remedy the drawbacks of the prior art, by providing a method and device for inserting a message in a sequence of digital images, which, whilst being robust to geometrical modifications and to the operations of compression and decompression, can be time re-synchronized on its extraction.
To this end, the invention provides a method of inserting a message in a sequence of images, the message comprising ordered symbols, characterized in that it comprises, for each image in which a symbol of the message is to be inserted, the steps of:                determining a first modulation sequence from a reference image included in the sequence of images, according to a first law, if the order of the symbol is different to a predetermined order,        determining a second modulation sequence from a reference image included in the sequence of images, according to a second law, if the order of the symbol is equal to the predetermined order,        modulating the symbol to be inserted by the determined modulation sequence,        inserting the modulated symbol in the current image.        
In a complementary manner, the invention relates to a device for the insertion of a message in a sequence of images, the message comprising ordered symbols, characterized in that is comprises:                means for determining, for each image in which a symbol of the message is to be inserted, a first modulation sequence from a reference image included in the sequence of images, according to a first law, if the order of the symbol is different to a predetermined order,        means for determining a second modulation sequence from a reference image included in the sequence of images, according to a second law, if the order of the symbol is equal to the predetermined order,        means for modulating the symbol to be inserted by the determined modulation sequence,        means for inserting the modulated symbol in the current image.        
The invention permits an insertion that is robust to geometrical distortions and to compression and decompression operations. Furthermore, in the case of a time truncation of the video sequence in which a message has been inserted, the invention makes it possible to re-synchronize this message on its extraction.
According to a preferred feature, the first and second sequences are such that the result of the correlation of the first sequence by the second sequence is negligible in relation to the result of the correlation of the first sequence by itself or of the second sequence by itself.
Thus it is possible to differentiate the symbols of the message which have been inserted using the first law from those which have been inserted using the second law.
According to a preferred feature, the reference image is the image following the current image in the sequence. This feature is simple to implement.
According to a preferred feature, the insertion is carried out in one image out of every two. This implementation is particularly simple, since a symbol can be inserted over the entirety of an image, this image being bounded by two images in which no insertion has been carried out. This implementation is simple and gives satisfactory results.
According to a preferred feature, the determination of a modulation sequence comprises:                performing integer division of a quantity dependent on the value of a predetermined component of each pixel of the reference image, by a first predetermined value,        comparing the remainder of the integer division with a second predetermined value, for each integer division,        determining the value of each coefficient of the modulation sequence, depending on the respective result of each comparison.        
According to a preferred feature, the predetermined order is that of the first symbol of the message. This is because it is particularly worthwhile to find the start of the message which has been inserted in the video sequence.
The invention also relates to a method of extracting a message from a sequence of images in which the message has been inserted by the method of insertion already set out, characterized in that it comprises the steps of:                detecting the images in which the symbol of predetermined order has been inserted, among the images in which a message symbol has been inserted,        extracting the inserted message.        
The message which is extracted is thus time re-synchronized, since the images in which the symbol of predetermined order has been inserted have been identified.
According to a preferred feature, the method of extraction further comprises the prior step of detecting the images in which a message symbol has been inserted.
This prior step makes it possible to simplify the search for the images in which the symbol of predetermined order has been inserted.
According to a preferred feature, the detection of the images in which the symbol of predetermined order has been inserted comprises, for an image in which a symbol has been inserted,                estimating the watermarking signal of the inserted symbol,        determining a demodulation sequence from a reference image, according to the second law,        measuring a correlation between the estimated watermarking signal and the demodulation sequence,        determining the images for which the correlation measurement is maximum.        
The calculated correlation measurements are maximum for the images in which the symbol of predetermined order has been inserted, which enables these images to be identified.
According to a preferred feature, the detection of the images in which a symbol has been inserted comprises, for an image:                estimating the watermarking signal of the inserted symbol,        determining a demodulation sequence from a reference image, according to the first law,        measuring a correlation between the estimated watermarking signal and the demodulation sequence,        determining the images for which the correlation measurement is maximum.        
The calculated correlation measurements are maximum for the images in which a symbol has been inserted, which enables these images to be identified.
According to a preferred feature, the method of extraction comprises, for an image in which a symbol has been inserted, the steps of:                estimating the watermarking signal of the inserted symbol,        determining a demodulation sequence from a reference image, according to a first or second law, depending on the order of the symbol,        demodulating the estimated watermarking signal with the demodulation sequence.        
The choice of the first or the second law is carried out depending on the knowledge of the images in which the symbol of predetermined order has been inserted.
The invention also relates to a device for extracting a message from a sequence of images in which the message has been inserted by the insertion device already presented, characterized in that it comprises:                means for detecting the images in which the symbol of predetermined order has been inserted, among the images in which a message symbol has been inserted,        means for extracting the inserted message.        
According to a preferred feature, the extraction device further comprises prior means for detecting the images in which a message symbol has been inserted.
In a fourth aspect, the object of the present invention is to remedy the drawbacks of the prior art, by providing a method and device for inserting a message in a sequence of digital images, which, whilst being robust to geometrical modifications and to the operations of compression and decompression, also makes it possible to extract the message inserted when the sequence of images in which the message was inserted has undergone a modification of a component of the value of the pixels.
To this end, the invention provides a method of inserting a message in a sequence of images, the images comprising pixels represented by components, characterized in that it comprises, for each image in which a symbol of the message is to be inserted, the steps of:                determining a modulation sequence from a reference image included in the sequence of images, according to a periodic law of predetermined period,        said law being such that the absolute value of a correlation measurement of the modulation sequence with a second modulation sequence determined according to the same law and from the same reference image in which the values of a predetermined component of the pixels have been modified, has only one maximum over the predetermined period,        modulating the symbol to be inserted by the determined modulation sequence,        inserting the modulated symbol in the current image.        
The invention enables insertion to be achieved that is robust in relation to geometric distortions and operations of compression and decompression, while also enabling the extraction of the inserted message when the sequence of images in which the message was inserted has undergone a modification of a component of the value of the pixels.
According to a preferred feature, the reference image is the image following the current image in the sequence. This feature is simple to implement.
According to a preferred feature, the insertion is carried out in one image out of every two. This implementation is particularly simple, since a symbol can be inserted over the entirety of an image, this image being bounded by two images in which no insertion has been carried out. This implementation is simple and gives satisfactory results.
According to a preferred feature, the determination of a modulation sequence comprises:                performing integer division of the value of a predetermined component of each pixel of the reference image, by a first predetermined value,        comparing the remainder of the integer division with a set of second predetermined values, for each integer division,        determining the value of each coefficient of the modulation sequence, depending on the respective result of each comparison.        
According to a preferred feature, the predetermined component is the luminance.
The invention also relates to a method of extracting a message from a sequence of images in which the message has been inserted by the method of insertion already set out, characterized in that it comprises the steps of:                estimating a modification of the values of the predetermined component of the pixels of the reference image, for each image in which a symbol has been inserted,        compensating for the estimated modification, for each image in which a symbol has been inserted,        extracting the inserted message.        
According to a preferred feature, the estimation of a modification of the values of the predetermined component of the pixels of the reference image comprises:                estimating the watermarking signal of the inserted symbol,        determining a demodulation sequence from a reference image in which the values of the predetermined component of the pixels have been modified,        measuring a correlation between the estimated watermarking signal and the demodulation sequence,        determining a modification value for which the correlation measurement is maximum.        
According to a preferred feature, the compensation comprises adding the estimated modification to the value of the predetermined component of each pixel of the reference image.
According to a preferred feature, the extraction comprises, for an image in which a symbol has been inserted, the steps of:                estimating the watermarking signal of the inserted symbol,        determining a demodulation sequence from a reference image, in which the values of the predetermined component of the pixels have been modified by the estimated modification,        demodulating the estimated watermarking signal with the demodulation sequence.        
In a complementary manner, the invention relates to a device for the insertion of a message in a sequence of images, the images comprising pixels represented by components, characterized in that is comprises:                means for determining, for each image in which a message symbol is to be inserted, a modulation sequence from a reference image included in the sequence of images, according to a periodic law of predetermined period,        said law being such that the absolute value of a correlation measurement of the modulation sequence with a second modulation sequence determined according to the same law and from the same reference image in which the values of a predetermined component of the pixels have been modified, has only one maximum over the predetermined period,        means for modulating the symbol to be inserted by the determined modulation sequence,        means for inserting the modulated symbol in the current image.        
The invention also concerns an extraction device which comprises means for implementing the above characteristics.
The insertion device and the extraction method and device have similar advantages to those already set out.
The invention also relates to a digital device including the device according to the invention, or means for implementing the method according to the invention. This digital apparatus is for example a digital camera, a digital camcorder, a scanner, a printer, a photocopier, or a fax machine. The advantages of the device and of the digital device are identical to those already set out.
The invention also concerns an information storage means, which can be read by a computer or microprocessor, integrated or not into the device, and possibly removable, stores a program implementing the method according to the invention.
The invention also concerns a computer program readable by a microprocessor and comprising one or more sequences of instructions is capable of implementing the methods according to the invention.